Miniature computers, commonly known as "hand-held computers" and "personal digital assistants," are becoming increasingly powerful and popular. The user interface included with one of these miniature computers typically includes a small "QWERTY" keyboard, a stylus, and a small touch-sensitive display screen, such as a liquid-crystal display (LCD). The size and speed of basic computer components has improved to the point where miniature computers can now perform many of the text-based functions, such as word processing, e-mail, spreadsheets, personal calendars, and the like that previously required a full-size desktop or laptop computer.
To use a miniature computer for one of these text-based functions, a user typically types on a keyboard to enter text and commands into an active data file, which is open within a host application program running on the computer. Other text input devices may include a voice recognition interface, a touch-sensitive screen that displays a graphical image of a keyboard, and a system that detects the motion of a stylus in combination with handwriting recognition software. The text and commands are then interpreted and manipulated by the host application program in accordance with the syntax and functionality implemented by the host application program.
For many users, the most time consuming computer activity is the entry of large amounts of text into various data files, such as word processing files, personal calendar files, e-mail files, and so forth. Regardless of the input method used, the speed at which the text can be entered into the computer is a major factor governing the user's efficiency. Entering text into a miniature computer can be particularly cumbersome using the small keyboards included with miniature computers. This is because the key size on this type of keyboard is so small that using one's finger to select a key runs a substantial risk of contacting one or more unintended keys. This sort of text entry error can slow text entry and frustrate the user.
Accordingly, effective text-input aids are important attributes for miniature computers. Due to space limitations, however, miniature computers typically carry significantly less computer storage, random-access memory, and processing capacity than their desktop and laptop cousins. In general, because processing speed and memory storage are more restricted for miniature computers, special attention must be given to these aspects of program design. As a result, text-input aids that are feasible to deploy on desktop and laptop computers may not be feasible to deploy on miniature computers. Text-input aids for miniature computers must therefore be designed in light of these relatively severe processing speed and memory-use constraints.
The designers of text-intensive application programs for conventional desktop and laptop computers have developed text-input aids to assist users in entering text into these computers. Although these text-input aids may not be directly applicable to miniature computers, they are generally instructive of the design techniques and considerations often associated with text-input aids. More specifically, the text-input aids developed for conventional desktop and laptop computers may be adapted for use in a miniature computer by modifying the text-input aids to operate with acceptable performance characteristics in view of the relatively severe processing speed and memory-use constraints encountered with the miniature computer.
A text completion system is a type of text-input aid that has been successfully deployed for conventional desktop and laptop computers. Generally stated, a text completion system predicts and suggests complete data entries based on partial data entries. This allows the user to type in a partial data entry and then accept a predicted text completion with a single keystroke, thus avoiding the keystrokes that would have been required to type the complete data entry. For example, a text prediction system may be configured to recognize a user's name so that the user's complete name, "Jossef Goldberg" for instance, may be predicted after the user types the first few letters, "Jos" in this example.
Because there are a limited number of words available in any given language, many of the words forming the vocabulary of the language are used frequently. This is particularly true for data files that include structured fields for certain data entries, such as the "from" and "to" fields of an e-mail message, and the "payee" and "amount" fields of a bank check. A structured field supplies a context for data to be entered into the field. This context can be used to limit the choice of text predictions for the field, and increase the likelihood that a suggested text completion will be correct. Text prediction systems therefore work well for structured data fields because the choice of words used in a particular structured field can often be sufficiently limited so that the word prediction system can offer reasonably likely suggestions within acceptable memory-use and performance characteristics.
Most-recently-used (MRU) text completion methods have also been deployed in connection with structured data fields to speed text entry and also serve as a memory aid for repetitive data entries. These text completion methods use an MRU data list for each structured field to provide a list of predicted text completion choices for the field. That is, a list of the most recent items entered into the structured field is used to predict text completions for partial data entries entered into the field. For example, a personal finance program may maintain a record of a person's previous bank checks. In order to speed entry of the check payee on a new check, the program keeps an MRU list of prior check payees. This MRU list is used to automatically predict a completion for the payee name after the first few letters of the payee have been typed by the user. For instance, if a user has previously written checks to "Georgia Power," the complete data entry "Georgia Power" may be predicted after the letters "Ge" have been typed into the check payee field.
In MRU text completion systems, an input character may be analyzed with respect to the prior history of text entered to predict the text likely to follow the input character or string of characters. Because MRU text prediction systems are based on a prior history of text entered, the search time and amount of storage required for the systems are important parameters. Either a linear or a binary search is typically used to scan the text history in order to predict a text completion. A linear search operates by sequentially examining each element in a list until the target element is found or the list has been completely processed. Because every entry must be analyzed, linear searches are primarily used with very short lists.
A binary search, on the other hand, locates an item by repeatedly dividing an ordered list in half and searching the half that it is known to contain the item. This requires a value for the input that can be compared against values in a list of items arranged in a known sequence, such as ascending numerical order corresponding to lexicographic placement. The binary search begins by comparing the input value against the value in the middle of the list. If the input value is greater than the middle value, the lower half of the list is discarded and the search continues on the upper half. The input value is again compared with a value in the middle of the new list and again half of the list is discarded. The process continues, with the input value being compared against the middle of each succeeding smaller list, until the desired item is found.
Although binary searches can generally be completed relatively quickly if the data to be searched is stored in a format allowing fast random access, both linear and binary searches can require substantial time to complete. This can lead to unacceptable performance when very large search lists must be analyzed. MRU text completion systems therefore tend to be costly in terms of computation resources and performance. Also, without a mechanism for increasing the likelihood of making a correct prediction, such as structured fields in the input data file, the text completion system may make wrong predictions so often that the system may be perceived as more annoying than useful. For this reason, MRU text completion systems have typically been deployed in connection with structured fields.
Restricting the search field using a limited text prediction data space, such as a known data range or naming syntax, is another approach to improving the performance of a text completion system. For example, a spreadsheet program may use the data entries in adjacent rows and columns as a limited data space list for predicting text completion choices when the user is entering a new heading into the spreadsheet. Similarly, an editing program for software development may use a predefined list of valid function and command names as a limited data space for predicting text completion choices when the user is writing a software program. Or a filing system may use the list of previously-created file names as a limited data space for predicting text completion choices when the user is selecting a file. Of course, these limited-data-space text prediction systems only work well when there is a limited and well-defined data space to use for selecting text predictions. They are not well suited to automatic application for all data entries in an unstructured portion of a data file because, in this situation, there is not a readily apparent limited and well-defined data space to use for selecting text prediction choices.
Prior text completion systems have additional shortcomings when deployed in the multiple-application-program environment that exists on most computers systems, including recent generations of miniature computers. These computers allow multiple application programs, such as a word processing program, an e-mail program, and a personal calendar program, to run simultaneously on the computer. User interfaces for the various application programs typically appear in different windows. The user selects one window at a time to receive input, and then inputs text and commands into the selected window using the keyboard or another text input device.
The text completion systems described above are usually deployed on an individual application program basis. That is, each text completion system is typically customized to work only with one particular application program. For example, the check writing text prediction system discussed previously works only with the check writing application program, and not with other application programs, such as a word processing program or e-mail program running on the same computer system. This causes wasteful duplication of software when similar text completion systems are implemented by several different application programs. Duplication of items stored in memory can also result. For example, duplicate items may be stored in memory when several different applications keep separate MRU histories or dictionaries. Another problem is that repetitive data entries cannot be identified across several application programs. As a result, the user may have to "teach" several text completion systems the same set of commonly-used data entries, such as the user's name, address, business name, etc.
As noted previously, all of the difficulties encountered with text completion systems in general are exacerbated in a text completion system for a miniature computer. Thus, there is a general need in the art for a text completion system for use with a miniature computer system having a touch-sensitive display screen and a reduced-size keyboard as primary data entry devices. There is a further need in the art for a text completion system that operates effectively within the restricted processing speed and memory-use characteristics of a miniature computer. There is a further need for an application-independent text completion system that may operate with multiple application programs running on a miniature computer.